#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
#include<algorithm>
using namespace std;

class Solution{
    public:
    bool ans1(string s, vector<string>& wordDict){
        int len = s.size(), l = wordDict.size();
        unordered_set<string> wordList;
        for(int i = 0; i != l; i++){
            wordList.insert(wordDict[i]);
        }
        vector<bool> dp(len+1);
        dp[0] = true;
        for(int i = 1; i != len+1; i++){
            for(int j = 0; j != i; j++){
                if(dp[j] && wordList.find(s.substr(j, i-j)) != wordList.end()){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
};

void test1(){
    Solution s;
    string str = "leetcode";
    vector<string> wordDict = {
        "leet",
        "code"
    };

    bool ret = s.ans1(str, wordDict);
    cout << ret << endl;
}

void test2(){
    Solution s;
    string str = "applepenapple";
    vector<string> wordDict = {
        "apple",
        "pen"
    };

    bool ret = s.ans1(str, wordDict);
    cout << ret << endl;
}

void test3(){
    Solution s;
    string str = "catsandog";
    vector<string> wordDict = {
        "cats",
        "dog",
        "sand",
        "and",
        "cat"
    };

    bool ret = s.ans1(str, wordDict);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}